package 力扣.回溯;

import java.util.ArrayList;
import java.util.List;

public class 数组总和III_216 {
    public List<List<Integer>> combinationSum3(int k, int n) {
         List<List<Integer>> ans = new ArrayList<>();
         List<Integer> box = new ArrayList<>();
         int sum = 0;
         backTrace(k,1,1,n,sum,ans,box);
         return ans;
    }

    private void backTrace(int k, int i, int pos,int n, int sum, List<List<Integer>> ans, List<Integer> box) {
        if (sum == n && i == k){
            ans.add(new ArrayList<>(box));
        }
        if (sum >= n || i >= k){
            return;
        }
        for (int j = pos; j <= 9; j++) {
            sum += j;
            box.add(j);
            backTrace(k, i + 1, j + 1, n, sum, ans, box);
            sum -= j;
            box.remove(box.size() - 1);
        }
    }
}
